package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/27/20
 * @Version 1.0
 */
/**
 * 选择排序
 * 将待排序序列分成未排序区和已排序区
 * 第一趟排序的时候整个待排序序列是未排序区
 * 每一趟排序其实就是从未排序区选择一个最值,放到已排序区
 * 跑len-1趟
 *
 * 原地排序
 * 不是一个稳定的算法,因为选择排序是从未排序区中找一个最值,并且和前面的元素交换位置,这会破坏稳定性
 * 时间复杂度:最好,最坏,平均都是O(n^2)
 *
 * @author jane
 */
public class SelectionSort {
    //选小的
    public int[] sortUp(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }
        int length = arr.length;
        for(int i=0;i<length-1;i++){
            int minIndex=i;
            for(int j=i+1;j<length;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            if(i!=minIndex){
                int temp = arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
        }

        return arr;
    }

    //选大的
    public int[] sortDown(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        int length=arr.length;
        for(int i=0;i<length-1;i++){
            int maxIndex=i;
            for(int j=i+1;j<length;j++){
                if(arr[j]>arr[maxIndex]){
                    maxIndex=j;
                }
            }
            if(maxIndex!=i){
                int temp=arr[i];
                arr[i]=arr[maxIndex];
                arr[maxIndex]=temp;
            }
        }

        return arr;
    }
}
